package a10_动态规划;

/**
 * <p>
 * a09_不同的二叉搜索树复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/1
 */
public class a09_不同的二叉搜索树复习3 {
    //二叉搜索树 左比中大 右比中小
    //1,2,3
    //1为根，左边0，右边2
    //2为根，左边1，右边1
    //3为根，左边2，右边0
    //dp[2] = 2
    //dp[1] = 1
    //dp[0] = 1
    //dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] + dp[0]
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = dp[i] + (dp[j] * dp[i-j-1]);
            }
        }
        return dp[n];
    }
}
